typedef struct binnode {
    type element;
    int rank;
    struct binnode* left;
    struct binnode* right;
} binnode;//树结点
typedef struct Bintree {
    binnode* root;
    int nodes;
    int depth;
} Bintree;//二叉树类
typedef Bintree* bintree;

bintree bintree_init(bintree that, int n)//生成二叉树, 按层次意义生成
{
    if (n == 0) {
        that = (bintree)malloc(sizeof(Bintree));
        that->root = NULL;
        return that;
    }

    int cnt = n;
    queue binnode_queue = queue_init(binnode_queue, cnt);
    that = (bintree)malloc(sizeof(Bintree));
    that->root = (binnode*)malloc(sizeof(binnode));
    queue_in(binnode_queue, (type)(void*)(that->root));
    cnt--;

    while (!queue_empty(binnode_queue)) {
        binnode* now = (binnode*)queue_out(binnode_queue).Void;
        if (cnt != n - 1) now = (binnode*)malloc(sizeof(binnode));
        queue_in(binnode_queue, (type)(void*)(now->left));
        queue_in(binnode_queue, (type)(void*)(now->right));
    }
    that->nodes = n;

    stack binnode_stack = stack_init(binnode_stack, that->nodes);
    binnode* temp = that->root;
    cnt = 0;

    while (true) {
        while (temp != NULL) {
            temp->rank = cnt;
            cnt++;
            stack_push(binnode_stack, (type)(void*)(temp->right));
            temp = temp->left;
        }
        if (stack_empty(binnode_stack)) break;
        temp = stack_pop(binnode_stack).Void;
    }
    return that;
}
void test_visit(binnode* now)
{
    printf("%d", now->element.Int);
}
void bintree_travpre(bintree that, void (*visit)(binnode*))//前序遍历, 接受visit方法,复杂度o(n),常系数大
{
    if(that->root == NULL) return;
    binnode* now = that->root;
    binnode* now_left = that->root->left;
    binnode* now_right = that->root->right;

    visit(now);
    that->root = now_left;
    bintree_travpre(that, visit);
    that->root = now_right;
    bintree_travpre(that, visit);
    that->root = now;

    return;
}
void bintree_travin(bintree that, void (*visit)(binnode*))//中序遍历, 接受visit方法,复杂度o(n),常系数大
{
    if (that->root == NULL) return;
    binnode* now = that->root;
    binnode* now_left = that->root->left;
    binnode* now_right = that->root->right;

    that->root = now_left;
    bintree_travin(that, visit);
    that->root = now;
    visit(now);
    that->root = now_right;
    bintree_travin(that, visit);
    that->root = now;

    return;
}
void bintree_travpost(bintree that, void (*visit)(binnode*))//后续遍历, 接受visit方法,复杂度o(n),常系数大
{
    if (that->root == NULL) return;
    binnode* now = that->root;
    binnode* now_left = that->root->left;
    binnode* now_right = that->root->right;

    that->root = now_left;
    bintree_travpost(that, visit);
    that->root = now_right;
    bintree_travpost(that, visit);
    that->root = now;
    visit(now);

    return;
}
void bintree_travlevel(bintree that, void (*visit)(binnode*))//层次遍历, 接受visit方法,复杂度o(n)
{
    queue binnode_queue = queue_init(binnode_queue, that->nodes);
    queue_in(binnode_queue, (type)(void*)that->root);

    while (!queue_empty(binnode_queue)) {
        binnode* now = (binnode*)queue_out(binnode_queue).Void;
        visit(now);
        queue_in(binnode_queue, (type)(void*)now->left);
        queue_in(binnode_queue, (type)(void*)now->right);
    }
}
binnode* bintree_find(bintree that, int n)//中序意义下内部搜索用, 时间复杂度O(logn)
{
    binnode* temp = that->root;
    while (temp == NULL) {
        if (n == temp->rank) return temp;
        else if (n < temp->rank) temp = temp->left;
        else temp = temp->right;
    }
    return temp;
}
type bintree_get(bintree that, int n)//中序意义下得到秩为n的元素, 时间复杂度O(logn)
{
    if (bintree_find(that, n) == NULL) return (type)0;
    else return bintree_find(that, n)->element;
}
int bintree_search(bintree that, type element)//判断是否存在, 时间复杂度O(logn)
{

}
bool bintree_exist(bintree that, type element)//包装search
{

}
bool bintree_put(bintree that, int n, type element)//中序意义下覆盖, 时间复杂端O(logn)
{

}
bool bintree_insert(bintree that, int n, type element)//中序遍历以义下的插入, 时间复杂度O(logn)
{

}
type bintree_remove(bintree that, int n)//中序意义下的删除, 时间复杂度O(logn)
{

}
/*void bintree_pretrav(bintree that, void (*visit)(binnode*))//迭代版版前序遍历
{
    stack binnode_stack = stack_init(binnode_stack, that->nodes);
    binnode* temp = that->root;

    while (true) {
        while (temp != NULL) {
            visit(temp);
            stack_push(binnode_stack, (type)(void*)(temp->right));
            temp = temp->left;
        }
        if (stack_empty(binnode_stack)) break;
        temp = stack_pop(binnode_stack).Void;
    }
}
void bintree_intrav(bintree that, void (*visit)(binnode*))//迭代版中序遍历
{
    stack binnode_stack = stack_init(binnode_stack, that->nodes);
    binnode* temp = that->root;

    while (true) {
        while (temp != NULL) {
            stack_push(binnode_stack, (type)(void*)(temp));
            temp = temp->left;
        }
        if (stack_empty(binnode_stack)) break;
        temp = stack_pop(binnode_stack).Void;
        visit(temp);
        temp = temp->right;
    }
}
void bintree_posttrav(bintree that, void (*visit)(binnode*))//迭代版后序遍历
{
    stack binnode_stack = stack_init(binnode_stack, that->nodes);
    binnode* temp = that->root;

    if (temp == NULL) stack_push(binnode_stack, (type)(void*)(temp));
    while (!stack_empty(binnode_stack)) {
        if (((binnode*)stack_top(binnode_stack).Void)->right != temp &&
            ((binnode*)stack_top(binnode_stack).Void)->right != temp
        ) {
            binnode* x;
            while ( x = (binnode*)stack_top(binnode_stack).Void ) {
            }
        }
    }
}*/ //非迭代版, 未实现






